public class SolutionInterview17_12 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode convertBiNode(TreeNode root) {
        return dfs(root)[0];
    }

    private TreeNode[] dfs(TreeNode root) {
        if (root==null){
            return new TreeNode[]{null,null};
        }
        TreeNode[] left=dfs(root.left);
        TreeNode[] right=dfs(root.right);
        root.left=null;
        TreeNode first;
        if (left[0]==null){
            first=root;
        }else {
            left[1].left=null;
            left[1].right=root;
            first=left[0];
        }
        TreeNode last;
        if (right[0]==null){
            last=root;
        }else {
            root.right=right[0];
            last=right[1];
        }
        return new TreeNode[]{first,last};
    }

    public static void main(String[] args) {
        System.out.println(new SolutionInterview17_12().convertBiNode(new TreeNode(2,new TreeNode(1),new TreeNode(3))).right.right.left);
    }
}
